package leetcode;

/*
386. 字典序排数
给定一个整数 n, 返回从 1 到 n 的字典顺序。
例如，
给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。
*/

import java.util.ArrayList;
import java.util.List;

public class problems_386 {
    public static void main(String[] args) {
        System.out.println(new Solution().lexicalOrder(123));
    }

    static class Solution {
        List<Integer> ret = new ArrayList<>();

        public List<Integer> lexicalOrder(int n) {
            for (int i = 1; i < 10; i++) {
                dfs(n, i);
            }
            return ret;
        }
        private void dfs(int n, int index) {
            if(index > n) return ;
            ret.add(index);
            for (int i = 0; i < 10; i++) {
                dfs(n, index * 10 + i);
            }
        }
    }
}